package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
 *  二叉树的最近公共祖先   递归
 * author: hongchen.liao
 * date:  2022/9/27
 */
public class _236_ {


      //Definition for a binary tree node.
      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }

    class Solution {
        TreeNode ans = null;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            dfs(root, p, q);
            return ans;
        }

        boolean dfs(TreeNode root, TreeNode p, TreeNode q){
            if(root == null){
                return false;
            }
            boolean lson = dfs(root.left, p, q);
            boolean rson = dfs(root.right, p, q);
            if((lson && rson) || (root.val == p.val || root.val == q.val) && (lson || rson) ){
                ans = root;
            }
            return lson || rson || (root.val == p.val || root.val == q.val);
        }
    }

}
